from collections import defaultdict


